/*
 * @lc app=leetcode.cn id=138 lang=cpp
 *
 * [138] 复制带随机指针的链表
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        vector<Node*> random1;          // 记录第一个链表中，节点的 random 指针
        map<Node*, int> mapper1;        // 记录第一个链表中，节点到下标的映射关系
        map<int, Node*> mapper2;        // 记录第二个链表中，下标到节点的映射关系

        int count = 0;                  // 遍历过程中的节点下标
        Node* currNode = nullptr;       // 遍历过程中的当前节点

        Node* dummyNode = new Node(0);   // 第二个链表的伪头部
        Node* prevNode = dummyNode;      // 第二个链表的前驱节点

        // 遍历第一个链表
        count = 0;
        currNode = head;
        while (currNode != nullptr) {
            // 记录第一个链表中 random 指针
            random1.push_back(currNode->random);
            mapper1[currNode] = count;
            
            // 创建第二个链表中的新节点
            Node* node = new Node(currNode->val);
            prevNode->next = node;
            prevNode = node;
            mapper2[count] = node;

            currNode = currNode->next;
            count++;
        }
        
        // 遍历第二个链表
        count = 0;
        currNode = dummyNode->next;
        while (currNode != nullptr) {
            // 更新第二个链表中的 random 指针
            if (random1[count] == nullptr) {
                currNode->random = nullptr;
            } else {
                // 将第一个链表中的 random 节点转化成下标
                int index = mapper1[random1[count]];
                // 将下标转化成第二个链表中的响应位置的节点
                currNode->random = mapper2[index];
            }

            currNode = currNode->next;
            count++;
        }
        
        return dummyNode->next;
    }
};
// @lc code=end

